package org.apache.commons.graph.algorithms.flow

import org.apache.commons.graph.CommonsGraph
import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.algorithms.flow.internal.FlowNetworkHandler
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.utils.Assertions
import org.apache.commons.graph.weight.OrderedMonoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Maximum Flow algorithm selector
 *
 * @param <V> the Graph vertices type
 * @param <WE> the Graph edges type
 * @param <W> the Graph weight type
</W></WE></V> */
interface MaxFlowAlgorithmSelector<V, WE, W> {
    /**
     * Calculates the maximum flow using the Edmonds-Karp algorithm.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the class responsible for operations on weights
     * @return the max flow calculate with Edmonds and Karp algorithm
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingEdmondsKarp(weightOperations: WO): W?

    /**
     * Calculates the maximum flow using the Ford-Fulkerson method.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the class responsible for operations on weights
     * @return the max flow calculate with Ford and Furkenson algorithm
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingFordFulkerson(weightOperations: WO): W?
}


/**
 * [MaxFlowAlgorithmSelector] implementation.
 *
 * @param <V> the Graph vertices type
 * @param <WE> the Graph edges type
 * @param <W> the Graph weight type
</W></WE></V> */
internal class DefaultMaxFlowAlgorithmSelector<V, WE, W>(
    private val graph: DirectedGraph<V, WE>,
    private val weightedEdges: Mapper<WE, W>,
    private val source: V,
    private val target: V
) : MaxFlowAlgorithmSelector<V, WE, W> {

    private class EdgeWrapper<WE>(val wrapped: WE? = null) {}

    //the algorithm isn't serializable.
    private class MapperWrapper<WE, W, WO : OrderedMonoid<W>>(
        private val weightOperations: WO,
        private val weightedEdges: Mapper<WE, W>
    ) : Mapper<EdgeWrapper<WE>, W> {

        override fun map(input: EdgeWrapper<WE>): W {
            if (input.wrapped == null) {
                return weightOperations.identity()
            }
            return weightedEdges.map(input.wrapped)
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingEdmondsKarp(weightOperations: WO): W? {
        //        val checkedWeightOperations = Assertions.checkNotNull(
//            weightOperations,
//            "Weight operations can not be null to find the max flow in the graph"
//        )

        // create flow network
        val flowNetwork = newFlowNetwok(graph, weightOperations)

        // create flow network handler
        val flowNetworkHandler =
            FlowNetworkHandler(
                flowNetwork, source, target, weightOperations,
                MapperWrapper(weightOperations, weightedEdges)
            )

        // perform breadth first search
        CommonsGraph.visit(flowNetwork).from(source).applyingBreadthFirstSearch(flowNetworkHandler)

        while (flowNetworkHandler.hasAugmentingPath()) {
            // update flow network
            flowNetworkHandler.updateResidualNetworkWithCurrentAugmentingPath()
            // look for another augmenting path with breadth first search
            CommonsGraph.visit(flowNetwork).from(source).applyingBreadthFirstSearch(flowNetworkHandler)
        }

        return flowNetworkHandler.onCompleted()
    }

    /**
     * {@inheritDoc}
     */
    override fun <WO : OrderedMonoid<W>> applyingFordFulkerson(weightOperations: WO): W? {
        val checkedWeightOperations = Assertions.checkNotNull(
            weightOperations,
            "Weight operations can not be null to find the max flow in the graph"
        )

        // create flow network
        val flowNetwork = newFlowNetwok(graph, checkedWeightOperations)

        // create flow network handler
        val flowNetworkHandler =
            FlowNetworkHandler(
                flowNetwork, source, target, checkedWeightOperations,
                MapperWrapper(checkedWeightOperations, weightedEdges)
            )

        // perform depth first search
        CommonsGraph.visit(flowNetwork).from(source).applyingDepthFirstSearch(flowNetworkHandler)

        while (flowNetworkHandler.hasAugmentingPath()) {
            // update flow network
            flowNetworkHandler.updateResidualNetworkWithCurrentAugmentingPath()
            // look for another augmenting path with depth first search
            CommonsGraph.visit(flowNetwork).from(source).applyingDepthFirstSearch(flowNetworkHandler)
        }

        return flowNetworkHandler.onCompleted()
    }

    private fun <WO : OrderedMonoid<W>> newFlowNetwok(
        graph: DirectedGraph<V, WE>,
        weightOperations: WO
    ): DirectedGraph<V, EdgeWrapper<WE>> {
        return CommonsGraph.newDirectedMutableGraph(object : AbstractGraphConnection<V, EdgeWrapper<WE>>() {
            override fun connect() {
                // vertices
                for (vertex in graph.vertices) {
                    addVertex(vertex)
                }
                // edges
                for (edge in graph.edges) {
                    val edgeVertices = graph.getVertices(edge)
                    val head = edgeVertices!!.head
                    val tail = edgeVertices.tail

                    addEdge(EdgeWrapper(edge)).from(head).to(tail)

                    if (graph.getEdge(tail, head) == null) {
                        // complete the flow network with a zero-capacity inverse edge
                        addEdge(EdgeWrapper()).from(tail).to(head)
                    }
                }
            }
        })
    }
}
